Daily Problem

If you are a beginner reading the material, you can start with a 26-day training of solving one problem per day.

Contest Link

Day 26: Air Conditioner

Air Conditioner

Sort the elements by its time, then you init with a valid range \([m, m]\) and for each element update and get the new valid range. If you get an invalid range in some element there is no answer.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

struct Client {
  ll t, l, h;
  Client () {}
  bool operator < (const Client& other) {
    if (t != other.t) return t < other.t;
    return l < other.l;
  }
};

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    ll n, m;
    cin >> n >> m;
    vector <Client> arr(n);
    for (int i = 0; i < n; i++) {
      cin >> arr[i].t >> arr[i].l >> arr[i].h;
    }
    sort(all(arr));
    pair <ll, ll> cur(m, m);
    bool ok = true;
    ll prev = 0;
    for (auto elem: arr) {
      ll d = elem.t - prev;
      pair <ll, ll> go(cur.first - d, cur.second + d);
      ll l = max(go.first, elem.l);
      ll r = min(go.second, elem.h);
      if (l > r) ok = false;
      cur.first = l;
      cur.second = r;
      prev = elem.t;
    }
    if (ok) cout << "YES\n";
    else cout << "NO\n";
  }
  return (0);
}

Day 25: Longest Palindrome

Longest Palindrome

Let the given words be \(s_1, s_2, \dots, s_n\). Then if we have \(s_i = s_j^R\) we just add them to our answer. Finally, we search if there is a word \(s_i = s_i^R\) than we can put in the middle of our answer.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector <string> s(n);
  vector <string> rs(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    rs[i] = s[i];
    reverse(all(rs[i]));
  }
  vector <bool> take(n, false);
  vector <pii> ans;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (take[i] or take[j]) continue;
      if (s[i] == rs[j]) {
        take[i] = take[j] = true;
        ans.pb(pii(i, j));
      }
    }
  }
  string add = "";
  for (int i = 0; i < n; i++) {
    if (take[i]) continue;
    if (s[i] == rs[i]) {
      add = s[i];
      break;
    }
  }
  string ret = "";
  string a = "", b = "", c = "";
  for (auto pp: ans) {
    a += s[pp.first];
  }
  b = add;
  c = a;
  reverse(all(c));
  ret = a + b + c;
  cout << sz(ret) << '\n';
  cout << ret << '\n';
  return (0);
}

Day 24: The ? 1 ? 2 ? … ? n = k problem

The ? 1 ? 2 ? … ? n = k problem

First, if \(n = 0\) the answer is \(3 (-1 -2 + 3)\), else let \(x\) be the minimum value such that \(sum = 1 + 2 + 3 + \dots + x \geq n\). Then if we substract the number \(y \leq x\) we will have \(sum - 2 \cdot y\). So, we need the the difference between \(sum - n\) to the even, else we should keep increasing \(sum\).

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  bool first = true;
  while (tc--) {
    if (not first) cout << '\n';
    first = false;
    int n;
    cin >> n;
    if (n == 0) {
      cout << 3 << '\n';
      continue;
    }
    n = abs(n);
    int sum = 0;
    int x = 1;
    while (sum < n) {
      sum += x;
      x++;
    }
    x--;
    while ((sum - n) % 2 == 1) {
      x++;
      sum += x;
    }
    cout << x << '\n';
  }
  return (0);
}

Day 23: Assigning to Classes

Assigning to Classes

Let sort the array, then in any possible partition it holds that \(ans \geq a_{n + 1} - a_n\) (can you prove it?), but in we put the student \(a_n\) alone in a class, then we get \(ans = a_{n + 1} - a_n\).

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    vi a(2 * n);
    for (int& elem: a) cin >> elem;
    sort(all(a));
    cout << a[n] - a[n - 1] << '\n';
  }
  return (0);
}

Day 22: Diverse Matrix

Diverse Matrix

Construct the matrix in this way:

\[ \begin{pmatrix} 2 & 2 \cdot (r + 2) & \cdots & 2 \cdot (r + c) \\ 3 & 3 \cdot (r + 2) & \cdots & 3 \cdot (r + c) \\ \vdots & \vdots & \ddots & \vdots \\ r + 1 & (r + 1) \cdot (r + 2) & \cdots & (r + 1) \cdots (r + c) \end{pmatrix} \]

We have that \(gcd(a, a + 1) = 1\)

Then, for each row (from 1 to r) we get these values \(2, 3, \dots, r + 1\) and for each column (from 1 to c) we get these values \(1, r + 2, r + 3, \dots, r + c\). That is, we get all the values in \([1, r + c]\) and there is no better answer (why?). So, we can implement a solution in \(O(rc)\) taking as special case when \(r = 1\), \(c = 1\) and \(r = c = 1\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int r, c;
  cin >> r >> c;
  if (r == 1 and c == 1) {
    cout << 0 << '\n';
    return (0);
  }
  if (r == 1) {
    for (int j = 0; j < c; j++) cout << 2 + j << " \n"[j == c - 1];
    return (0);
  }
  if (c == 1) {
    for (int i = 0; i < r; i++) cout << 2 + i << '\n';
    return (0);
  }
  vector <vector <int>> mat(r, vector <int> (c));
  for (int i = 0; i < r; i++) mat[i][0] = 2 + i;
  for (int i = 0; i < r; i++) {
    int p = r + 2;
    for (int j = 1; j < c; j++) {
      mat[i][j] = mat[i][0] * p;
      p++;
    }
  }
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) cout << mat[i][j] << " \n"[j == c - 1];
  }
  return (0);
}

Day 21: Dice Tower

Dice Tower

The sum of opposite faces in a dice is always 7, then if we have \(x\) dices, each dice contributes with \(14 \cdot x\) and the top dice contributes with one more number between \(1\) and \(6\). Then, we have:

\[14 \cdot x + d = n\]

Where \(1 \leq d \leq 6\). So, if the equation holds for some \(1 \leq x\) we have and answer.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    ll num;
    cin >> num;
    bool ok = false;
    for (int d = 1; d <= 6; d++) {
      ll val = num - d;
      if (val % 14 == 0 and val / 14 >= 1) ok = true;
    }
    if (ok) cout << "YES\n";
    else cout << "NO\n";
  }
  return (0);
}

Day 20: Maximize an Expression

Maximize an Expression

We have \(\sum k_i \cdot x_i = 0\) and we want to maximize:

\[F = \sum \sqrt{x_i + c_i}\]

We can solve it using Cauchy-Schwarz inequality, is states that:

\[(\sum a_1 \cdot b_i)^2 \leq (\sum a_i^2) \cdot (\sum b_i^2)\]

And it becomes and equality when \(\frac{a_i}{b_i} = constant\)

Then, if we take \(a_i = \sqrt{k_i (x_i + c_i)}\) and \(b_i = \sqrt{\frac{1}{k_i}}\) we get:

\[(\sum \sqrt{x_i + c_i})^2 = F^2 \leq (\sum k_i (x_i + c_i)) \cdot (\sum \frac{1}{k_i})\]

But \(\sum k_i \cdot x_i = 0\), then we get:

\[F^2 \leq (\sum k_i \cdot c_i) \cdot (\sum \frac{1}{k_i})\]

Using it we can get if \(F\) exists. Moreover, using \(\frac{a_i}{b_i} = constant\) and \(\sum k_i \cdot x_i = 0\) we get that:

\[x_i = \frac{\sum k_j \cdot c_j}{k_i^2 \cdot (\sum 1 / k_j)} - c_i\]

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    vector <double> k(n);
    for (auto& elem: k) cin >> elem;
    vector <double> c(n);
    for (auto& elem: c) cin >> elem;
    double prod_sum = 0;
    double inv_sum = 0;
    for (int i = 0; i < n; i++) {
      prod_sum += c[i] * k[i];
      inv_sum += 1 / k[i];
    }
    assert(0 < inv_sum);
    if (prod_sum < 0) {
      cout << -1 << '\n';
      continue;
    }
    double F = 0;
    vector <double> x(n);
    for (int i = 0; i < n; i++) {
      x[i] = prod_sum / (k[i] * k[i] * inv_sum) - c[i];
      F += sqrt(x[i] + c[i]);
    }
    cout << fixed << setprecision(9);
    cout << F;
    for (int i = 0; i < n; i++) {
      cout << ' ' << x[i];
    }
    cout << '\n';
  }
  return (0);
}

Day 19: Jimmy’s Balls

Jimmy’s Balls

We have \(1 \leq r < b < g \land r + b + g = n\)

If we fix \(r\), we have \(b + g = n - r = m\)

Then, these are the values that hold the equation:

• \(b = 1 \to g = m - 1\)
• \(b = 2 \to g = m - 2\)
• \(\vdots\)
• \(b = k \to g = m - k\)

But \(b < g \to k < m - k \to 2 \cdot k < m \land r < k\). So, \(k = max(0, \frac{m}{2} - [m \bmod 2 = 0] - r)\). Using it we can implement a \(O(n)\) solution for each case.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc = 0;
  ll n;
  while (cin >> n, n != 0) {
    ll ans = 0;
    for (ll r = 1; r < n; r++) {
      ll m = n - r;
      ll k = m / 2;
      if (m % 2 == 0) k--;
      ans += max(0LL, k - r);
    }
    cout << "Case " << ++tc << ": " << ans << '\n';
  }
  return (0);
}

Day 18: Consecutive Integers

Consecutive Integers

If the answer is \(l + (l + 1) + \dots + (l + d - 1) = n\)

Then, we have:

\[\binom{l + d - 1}{2} - \binom{l - 1}{2} = n\] \[l = \frac{2 \cdot n - d^2 + d}{2 \cdot d}\]

So, we can fix \(d\) and implement a brute force solution.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  while (cin >> n, n != -1) {
    int ans_l, ans_r;
    for (int d = 1; d * d <= 2 * n; d++) {
      int sum = 2 * n - d * d + d;
      if (sum % (2 * d) == 0) {
        ans_l = sum / (2 * d);
        ans_r = ans_l + d - 1;
      }
    }
    cout << n << " = " << ans_l << " + ... + " << ans_r << '\n';
  }
  return (0);
}

Day 17: GCD on Blackboard

GCD on Blackboard

If we change the \(i\)-th element then, we have:

\[g = gcd(gcd(A_1, A_2, \dots, A_{i - 1}), gcd(A_{i + 1}, A_{i + 2}, \dots, A_n))\]

And we know that \(gcd(a, b) \leq \min(a, b) \land gcd(a, a) = a\)

So, we can choose to replace \(a_i\) with \(g\) and we will get \(g = gcd(g, A_i)\). Finally, we can use the idea of prefix sums and try to replace every \(i\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> arr(n);
  vector <int> l(n), r(n);
  for (int i = 0; i < n; i++) cin >> arr[i];
  l[0] = arr[0];
  for (int i = 1; i < n; i++) l[i] = __gcd(l[i - 1], arr[i]);
  r[n - 1] = arr[n - 1];
  for (int i = n - 2; i >= 0; i--) r[i] = __gcd(r[i + 1], arr[i]);
  int ans = max(l[n - 2], r[1]);
  for (int i = 1; i + 1 < n; i++) ans = max(ans, __gcd(l[i - 1], r[i + 1]));
  cout << ans << endl;
  return (0);
}

Day 16: DivRem Number

DivRem Number

There is some problem in the rendering of the statement. It should say:

\[\lfloor \frac{N}{m} \rfloor = N \bmod m\]

Solution:

We known from the division theorem that:

\[N = \lfloor \frac{N}{m} \rfloor \cdot m + N \bmod m\]

Let \(k = \lfloor \frac{N}{m} \rfloor = N \bmod m\)

Then, we have:

\[N = k \cdot m + k\] \[N = k \cdot (m + 1)\]

Then, m + 1 must be a divisor of \(N\), so we can generate all the divisors of \(N\) and check if the condition holds in \(O(\sqrt{N})\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n;
  cin >> n;
  vector <ll> div;
  for (ll d = 1; d * d <= n; d++) {
    if (n % d == 0) {
      if (d != 1) div.push_back(d);
      if (d != n / d) div.push_back(n / d);
    }
  }
  ll ans = 0;
  for (ll d: div) {
    ll m = d - 1;
    if (n % m == n / m) {
      ans += m;
    }
  }
  cout << ans << endl;
  return (0);
}

Day 15: ConneR and the A.R.C. Markland-N

ConneR and the A.R.C. Markland-N

There are \(k\) closed restaurants, thefore we will find the answer in \(O(k)\) steps, so a brute force solution in enough.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    int n, s, k;
    cin >> n >> s >> k;
    set <int> st;
    for (int i = 0; i < k; i++) {
      int a;
      cin >> a;
      st.insert(a);
    }
    int ans = INT_MAX;
    for (int d = 0; ; d++) {
      for (int sign: {1, -1}) {
        int cur = s + sign * d;
        if (1 <= cur and cur <= n and st.count(cur) == 0) {
          ans = d;
        }
      }
      if (ans != INT_MAX) break;
    }
    cout << ans << '\n';
  }
  return (0);
}

Day 14: Resale

Resale

Each element can be added to \(X\) or to \(Y\).

Let \(b = b_nb_{n - 1} \dots b_1\) be a bit mask where \(b_i = 1\) if the \(i\)-th element is taken and \(b_i = 0\) if the \(i-th\) is not taken, then we realize that all possible masks are \(b \in [0, 2 ^n)\). In this way, we can implement an \(O(n 2^n)\) solution and that is enough.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> v(n), c(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  for (int i = 0; i < n; i++) cin >> c[i];
  int ans = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    int x = 0, y = 0;
    for (int bit = 0; bit < n; bit++) if ((mask >> bit) & 1) x += v[bit], y += c[bit];
    ans = max(ans, x - y);
  }
  cout << ans << endl;
  return (0);
}

We can also implement the above idea using backtracking.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

int n;
vi v, c;

int backtrack (int pos, int x, int y) {
  if (pos == n) return x - y;
  return max(backtrack(pos + 1, x + v[pos], y + c[pos]), backtrack(pos + 1, x, y));
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  v.resize(n);
  c.resize(n);
  for (int& elem: v) cin >> elem;
  for (int& elem: c) cin >> elem;
  cout << backtrack(0, 0, 0) << '\n';
  return (0);
}

There is another solution. If we take the elements \(i_1, i_2, \dots, i_k\) then we have:

\[(v_{i_1} + v_{i_2} + \dots v_{i_k}) - (c_{i_1} + c_{i_2} + \dots + c_{i_k})\]

We can write the above expression in this way:

\[(v_{i_1} - c_{i_1}) + (v_{i_2} - c_{i_2}) + \dots + (v_{i_k} - c_{i_k})\]

Therefore, if \(v_{i} - c_{i}\) is positive, we take the \(i-th\) element, else we do not.

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

int n;
vi v, c;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  v.resize(n);
  c.resize(n);
  for (int& elem: v) cin >> elem;
  for (int& elem: c) cin >> elem;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] - c[i] > 0) ans += v[i] - c[i];
  }
  cout << ans << '\n';
  return (0);
}

Day 13: Exception Handling

Exception Handling

First solution: Notice that the answer will allways be the greatest value or the second greatest value. We can find these values in \(O(n)\) or in \(O(n \log n)\).

Code

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vi A(n);
  for (int& elem: A) cin >> elem;
  vi B = A;
  sort(rall(B));
  for (int elem: A) {
    if (elem != B[0]) cout << B[0] << '\n';
    else cout << B[1] << '\n';
  }
  return (0);
}

Second solution: We need to compute:

\[\max(A_1, A_2, \dots, A_{i - 1}), \max(A_{i}, A_{i + 1}, \dots, A_{n})\]

Let:

\[left[0] = 0\] \[left[i] = \max(left[i - 1], A[i])\]

\[right[n + 1] = 0\] \[right[n] = \max(right[n + 1], A[i])\]

Then, we need to compute: \(\max(left[i - 1], right[i + 1])\), but we can compute \(left\) and \(right\) in \(O(n)\) using the idea of prefix sums. Therefore, we can solve the problem in \(O(n)\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> arr(n + 1);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  vector <int> left(n + 1);
  left[0] = 0;
  for (int i = 1; i <= n; i++) left[i] = max(left[i - 1], arr[i]);
  vector <int> right(n + 2);
  right[n + 1] = 0;
  for (int i = n; i >= 0; i--) right[i] = max(right[i + 1], arr[i]);
  for (int i = 1; i <= n; i++) cout << max(left[i - 1], right[i + 1]) << '\n';
  return (0);
}

Day 12: Green Bin

Green Bin

If \(s \land t\) are anagrams, then \(sort(all(a)) = sort(all(b))\). That is, if we sort the letters of a string, we have a representative of a set of anagrams. Moreover, if we have \(x\) strings of the same anagram class, we can choose \(\binom{x}{2}\) indices such that \(s_i \land s_j\) are anagrams. In this way, we can implement a solution in \(O(N \log N)\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  map <string, int> mp;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort(all(s));
    mp[s]++;
  }
  ll ans = 0;
  for (auto pp: mp) {
    ll cnt = pp.second;
    ans += cnt * (cnt - 1) / 2;
  }
  cout << ans << '\n';
  return (0);
}

Day 11: Blocks

Blocks

Each block should end up being black or white. You can fix what color the string will be and try to change it in a loop (if you are in iteration i you have already change \(s[0: i - 1]\), now if \(s[i] \not = \text{the color you have fixed}\), invert \(s[i], s[i + 1]\)). In this way you need at most \(n - 1\) operations.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

void solve (string s, char ch) {
  vector <int> ans;
  for (int i = 0; i + 1 < sz(s); i++) {
    if (s[i] != ch) {
      s[i] = ch;
      s[i + 1] = (s[i + 1] == 'B') ? 'W' : 'B';
      ans.pb(i + 1);
    }
  }
  if (s.back() != ch) return;
  cout << sz(ans) << '\n';
  for (int elem: ans) cout << elem << ' ';
  exit(0);
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  solve(s, 'W');
  solve(s, 'B');
  cout << -1 << '\n';
  return (0);
}

Day 10: JOE is on TV!

JOE is on TV!

You can notice that the optimal strategy is that in each turn one opponent fails to answer. Then, our answer is

\[\frac{1}{n} + \frac{1}{n - 1} + \frac{1}{n - 2} + \dots + \frac{1}{1}\]

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  long double sum = 0;
  for (int i = 1; i <= n; i++) {
    long double x = i;
    sum += 1.0 / x;
  }
  cout << fixed << setprecision(12) << sum << '\n';
  return (0);
}

Day 09: Number of Triplets

Number of Triplets

If you fix \(A, C\) with two fors, you can get what value of \(B\) you need. Moreover, as all the points are integers, we can check if \(A_x + C_x \land A_y + C_y\) are even in order to avoid working with floats. Now, we have fixed \(B = ((A_x + C_x) / 2, (A_y + C_y) / 2)\) and we need to check if this point is in the input. We can do it with a set (you’ll get TLE with a map) and solve the problem in \(O(n^2 \log n)\).

Code

#include <bits/stdc++.h>

using namespace std;

int main () {
  int n;
  cin >> n;
  vector <pair <int, int>> point(n);
  set <pair <int, int>> st;
  for (int i = 0; i < n; i++) {
    cin >> point[i].first >> point[i].second;
    st.insert(point[i]);
  }
  int ans = 0;
  for (int a = 0; a < n; a++) {
    for (int c = a + 1; c < n; c++) {
      pair <int, int> b;
      int x = point[a].first + point[c].first;
      int y = point[a].second + point[c].second;
      if (x % 2 or y % 2) continue;
      b.first = x / 2;
      b.second = y / 2;
      if (st.count(b)) ans++;
    }
  }
  cout << ans << endl;
  return (0);
}

Furthermore, you can check if a point is in the input in \(O(1)\) storing the points in a matrix of booleans. But, as the coordinates can take negative values in \([-1000, 1000]\) you can associate to each number \((x, y) \to (x + 1000, y + 1000)\) (this is a biyection). Using it, each coordinate is non-negative, so we can store it in our matrix.

Day 08: Little Quilt

Little Quilt

Just simulate what the problem says.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

char rotate (char ch) {
  if (ch == '/') return '\\';
  if (ch == '\\') return '/';
  if (ch == '+') return '+';
  if (ch == '-') return '|';
  if (ch == '|') return '-';
}

struct Quilt {
  int n, m;
  vector <string> grid;
  Quilt () {}
  Quilt (char ch) {
    if (ch == 'A') {
      grid.push_back("//");
      grid.push_back("/+");
    }
    if (ch == 'B') {
      grid.push_back("--");
      grid.push_back("--");
    }
    n = m = 2;
  }
  Quilt turn () {
    vector <string> turned(m, string(n, ' '));
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) {
        turned[c][n - 1 - r] = rotate(grid[r][c]);
      }
    }
    Quilt ret;
    ret.grid = turned;
    ret.m = n;
    ret.n = m;
    return ret;
  }
  Quilt sew (Quilt other) {
    vector <string> join(n, string(m + other.m, ' '));
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) {
        join[r][c] = grid[r][c];
      }
      for (int c = 0; c < other.m; c++) {
        join[r][m + c] = other.grid[r][c];
      }
    }
    Quilt ret;
    ret.grid = join;
    ret.n = n;
    ret.m = m + other.m;
    return ret;
  }
  void print () {
    for (string row: grid) cout << row << '\n';
  }
};

bool solve (string& command) {
  stack <int> op;
  vector <Quilt> ans;
  string cur = "";
  for (char ch: command) {
    if (ch == '(') {
      if (cur == "turn") op.push(1);
      else if (cur == "sew") op.push(2);
      else return false;
      cur = "";
    } else if (ch == ')') {
      if (not cur.empty()) {
        if (cur == "A") ans.push_back(Quilt('A'));
        else if (cur == "B") ans.push_back(Quilt('B'));
        else return false;
        cur = "";
      }
      if (op.empty()) return false;
      int option = op.top();
      op.pop();
      if (option == 1) {
        if (ans.size() < 1) return false;
        ans.back() = ans.back().turn();
      } else if (option == 2) {
        if (ans.size() < 2) return false;
        Quilt a = end(ans)[-2];
        Quilt b = end(ans)[-1];
        ans.pop_back();
        ans.pop_back();
        if (a.n != b.n) return false;
        ans.push_back(a.sew(b));
      }
    } else if (ch == ',') {
      if (cur != "") {
        if (cur == "A") ans.push_back(Quilt('A'));
        else if (cur == "B") ans.push_back(Quilt('B'));
        else return false;
      }
      cur = "";
    } else {
      cur += ch;
    }
  }
  if (ans.size() != 1) return false;
  ans[0].print();
  return true;
}

int main () {
  int tc = 0;
  char ch;
  string command = "";
  while ((ch = getchar()) != EOF) {
    if (ch == ' ' or ch == '\n') continue;
    if (ch == ';') {
      printf("Quilt %d:\n", ++tc);
      if (not solve(command)) puts("error");
      command = "";
    } else {
      command += ch;
    }
  }
  return (0);
}

Day 07: z-sort

z-sort

Sort the array and alternate taking elements (the smallest, the greater, the second smallest, the second greater, …).

Code

#include <bits/stdc++.h>

using namespace std;

int main () {
  int n;
  cin >> n;
  vector <int> arr(n);
  for (int i = 0; i < n; i++) cin >> arr[i];
  sort(begin(arr), end(arr));
  int l = 0, r = n - 1;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) cout << arr[l++];
    else cout << arr[r--];
    cout << " \n"[i == n - 1];
  }
  return (0);
}

Day 06: GeT AC

GeT AC

We can count how many AC there are in a range using prefix sums and taking care or corner cases.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector <int> ac(n + 1, 0);
  for (int i = 1; i < n; i++) {
    if (s[i - 1] == 'A' and s[i] == 'C') {
      ac[i + 1] = 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    ac[i] += ac[i - 1];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    int x = ac[r] - ac[l - 1];
    if (ac[l] - ac[l - 1] == 1) x--;
    cout << x << '\n';
  }
  return (0);
}

Day 05: Competitive Programmer

Competitive Programmer

\(60 = 3 \cdot 5 \cdot 2 \cdot 2\). Then, to verify that we can construct a number multiple of \(60\) it is enough to verify:

• It is multiple of 3: the sum of digits is multiple of 3
• It is multiple of 5 and 2: It ends in 0
• It is multiple of 4: the last two digits are multiple of 4

Code

#include <bits/stdc++.h>
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  while (n--) {
    string s;
    cin >> s;
    if (sz(s) == 1) {
      if (s[0] == '0') cout << "red\n";
      else cout << "cyan\n";
      continue;
    }
    int zero = 0;
    int sum = 0;
    for (auto ch: s) zero += (ch == '0'), sum += (ch - '0');
    if (sum % 3 or !zero) {
      cout << "cyan\n";
      continue;
    }
    if (zero > 1) {
      cout << "red\n";
      continue;
    }
    bool ok = false;
    for (char ch: s) {
      if (ch == '0') continue;
      int num = (ch - '0') * 10;
      if (num % 4 == 0) ok = true;
    }
    if (ok) cout << "red\n";
    else cout << "cyan\n";
  }
  return (0);
}

Day 04: 0 or 1 Swap

0 or 1 Swap

Try every \(i, j\). This solution is \(O(N^3)\) and as \(N \leq 50\) it is enough.

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> arr(n);
  for (int i = 0; i < n; i++) cin >> arr[i];
  vector <int> s = arr;
  sort(all(s));
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      swap(arr[i], arr[j]);
      if (arr == s) {
        cout << "YES\n";
        return (0);
      }
      swap(arr[i], arr[j]);
    }
  }
  cout << "NO\n";
  return (0);
}

Day 03: Brick Break

Brick Break

The problem is basically to find the largest continuous segment \([l, r] \mid a[l + i] = i + 1, 0 \leq i \leq r - l\). Notice that we can do it in \(O(n)\).

Code

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  int cnt = 0;
  int cur = 1;
  for (int i = 0; i < n; i++) {
    int elem;
    cin >> elem;
    if (elem == cur) cur++, cnt++;
  }
  int need = n - cnt;
  if (need <= n - 1) cout << need << '\n';
  else cout << -1 << '\n';
  return (0);
}

Day 02: Prime Subtraction

Prime Subtraction

If \(x - y = 1\) then the answer is no, else, by the fundamental theorem of arithmetic \(\exists \, p\) prime \(: p | (x - y)\). So, the answer is yes.

Code

#include <bits/stdc++.h>

using namespace std;

int main () {
  int tc;
  cin >> tc;
  while (tc--) {
    long long x, y;
    cin >> x >> y;
    if (x - y == 1) cout << "NO\n";
    else cout << "YES\n";
  }
  return (0);
}

Day 01: Superhero Transformation

Superhero Transformation

Let \(f(c) = 1\) if c is as vowel and \(f(c) = 0\) otherwise. Then, the answer is true iff \(|s| = |t| \land f(s[i]) = f(t[i]) \quad \forall i \in [0, n)\).

Code

#include <bits/stdc++.h>

using namespace std;

int f (char c) {
  if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u') return 1;
  return 0;
}

int main () {
  string s, t;
  cin >> s >> t;
  if (s.size() != t.size()) {
    cout << "No" << '\n';
    return (0);
  }
  bool ok = true;
  for (int i = 0; i < s.size(); i++) {
    if (f(s[i]) != f(t[i])) ok = false;    
  }
  if (ok) cout << "Yes\n";
  else cout << "No\n";
  return (0);
}